//
// Created by Lenovo on 2021/3/15.
//

#include "sort.h"

#include <iostream>

using namespace std;

void bubbleSwapSort(int *list, int len) {
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < len - i; j++) {
            int d = j + 1;
            if (d < len - i && list[d] < list[j]) {
                int tmp = list[d];
                list[d] = list[j];
                list[j] = tmp;
            }
        }
    }
}

int findPart(int *list, int low, int high) {
    int newValue = list[low];
    while (low < high) {
        for (; list[high] > newValue && high > low; high--);
        list[low] = list[high];

        for (; list[low] < newValue && high > low; low++);
        list[high] = list[low];
    }
    list[low] = newValue;
    return low;
}

void doQuickSwapSort(int *list, int low, int high) {
    if (low < high) {
        int place = findPart(list, low, high);
        doQuickSwapSort(list, low, place - 1);
        doQuickSwapSort(list, place + 1, high);
    }
}

void quickSwapSort(int *list, int len) {
    doQuickSwapSort(list, 0, len - 1);
}

